/*
    二叉树是一种常见的数据结构，包含节点和分支，每个节点最多有两个子节点。实现二叉树的创建和遍历可以用于许多场景，如搜索、排序和数据组织。

创建二叉树
创建二叉树需要定义节点结构和相关操作，例如插入节点、构建树等。为了简单起见，我们使用以下方法：

创建二叉树节点。
插入节点到二叉树。
创建二叉树。
遍历二叉树
二叉树的遍历有三种主要方式：

前序遍历：先访问根节点，再遍历左子树，最后遍历右子树。
中序遍历：先遍历左子树，再访问根节点，最后遍历右子树。
后序遍历：先遍历左子树，再遍历右子树，最后访问根节点

代码要点
定义了二叉树节点 TreeNode，包括数据和左、右子节点。
使用 insert 函数将数据插入二叉树中。
使用前序、中序、后序遍历函数对树进行遍历。
提供了示例数据并演示了三种遍历方式。
这段代码是一个简单的二叉树创建和遍历示例，适用于学习和基本操作。根据需求，你可以扩展这些代码来实现更多高级功能，如查找、删除、平衡等。


层序遍历（或称为宽度优先遍历）是一种遍历二叉树的方式，按照树的层次从上到下、从左到右的顺序进行遍历。通常使用队列（queue）来辅助实现层序遍历。
*/

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 定义二叉树节点
typedef struct TreeNode {
    int data; // 节点数据
    struct TreeNode* left; // 左子节点
    struct TreeNode* right; // 右子节点
} TreeNode;

// 定义队列节点
typedef struct QueueNode {
    TreeNode* treeNode; // 二叉树节点
    struct QueueNode* next; // 指向下一个队列节点
} QueueNode;

// 定义队列
typedef struct Queue {
    QueueNode* front; // 队列头
    QueueNode* rear; // 队列尾
} Queue;

// 创建新的队列
Queue* createQueue() {
    Queue* queue = (Queue*)malloc(sizeof(Queue)); // 创建队列
    queue->front = NULL; // 初始化队列头
    queue->rear = NULL; // 初始化队列尾
    return queue;
}

// 入队操作
void enqueue(Queue* queue, TreeNode* treeNode) {
    QueueNode* newQueueNode = (QueueNode*)malloc(sizeof(QueueNode));
    newQueueNode->treeNode = treeNode;
    newQueueNode->next = NULL;
    if (queue->rear == NULL) { // 队列为空
        queue->front = queue->rear = newQueueNode; // 设置头和尾
    } else {
        queue->rear->next = newQueueNode; // 链接新的队列节点
        queue->rear = newQueueNode; // 更新队列尾
    }
}

// 出队操作
TreeNode* dequeue(Queue* queue) {
    if (queue->front == NULL) { // 队列为空
        return NULL;
    }
    QueueNode* temp = queue->front; // 获取头节点
    TreeNode* treeNode = temp->treeNode;
    queue->front = queue->front->next; // 更新队列头
    if (queue->front == NULL) { // 如果队列变空
        queue->rear = NULL;
    }
    free(temp); // 释放队列节点
    return treeNode;
}

// 检查队列是否为空
bool isQueueEmpty(Queue* queue) {
    return queue->front == NULL; // 如果队列头为空，则队列为空
}

// 创建新的二叉树节点
TreeNode* createNode(int data) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode)); // 创建新的二叉树节点
    node->data = data; // 设置数据
    node->left = NULL; // 初始化左子节点
    node->right = NULL; // 初始化右子节点
    return node;
}

// 插入节点到二叉树
TreeNode* insert(TreeNode* root, int data) {
    if (root == NULL) { // 如果根节点为空
        return createNode(data);
    }

    if (data < root->data) { // 数据小于根节点，则插入到左子树
        root->left = insert(root->left, data);
    } else { // 否则插入到右子树
        root->right = insert(root->right, data);
    }

    return root;
}

// 前序遍历
void preOrderTraversal(TreeNode* root) {
    if (root == NULL) return;
    printf("%d ", root->data); // 打印根节点
    preOrderTraversal(root->left); // 前序遍历左子树
    preOrderTraversal(root->right); // 前序遍历右子树
}

// 中序遍历
void inOrderTraversal(TreeNode* root) {
    if (root == NULL) return;
    inOrderTraversal(root->left); // 中序遍历左子树
    printf("%d ", root->data); // 打印根节点
    inOrderTraversal(root->right); // 中序遍历右子树
}

// 后序遍历
void postOrderTraversal(TreeNode* root) {
    if (root == NULL) return;
    postOrderTraversal(root->left); // 后序遍历左子树
    postOrderTraversal(root->right); // 后序遍历右子树
    printf("%d ", root->data); // 打印根节点
}

// 层序遍历
void levelOrderTraversal(TreeNode* root) {
    if (root == NULL) return; // 空树时直接返回

    Queue* queue = createQueue(); // 创建队列
    enqueue(queue, root); // 根节点入队

    while (!isQueueEmpty(queue)) { // 当队列不为空
        TreeNode* currentNode = dequeue(queue); // 出队并访问节点
        printf("%d ", currentNode->data); // 打印节点数据
        
        if (currentNode->left != NULL) { // 左子节点入队
            enqueue(queue, currentNode->left);
        }
        if (currentNode->right != NULL) { // 右子节点入队
            enqueue(queue, currentNode-> right);
        }
    }

    free(queue); // 释放队列
    printf("\n");
}

// 主函数
int main() {
    TreeNode* root = NULL;

    int values[] = {10, 5, 15, 3, 7, 13, 17}; // 示例数据
    for (int i = 0; i < 7; i++) {
        root = insert(root, values[i]); // 将示例数据插入二叉树
    }

    printf("Pre-order traversal: "); // 前序遍历
    preOrderTraversal(root);
    printf("\n");

    printf("In-order traversal: "); // 中序遍历
    inOrderTraversal(root);
    printf("\n");

    printf("Post-order traversal: "); // 后序遍历
    postOrderTraversal(root);
    printf("\n");

    printf("Level-order traversal: "); // 层序遍历
    levelOrderTraversal(root);
    printf("\n");

    return 0;
}
/*
    代码要点
新增了队列数据结构来辅助层序遍历，包括创建、入队、出队、队列是否为空等操作。
在主函数中，插入示例数据到二叉树并分别进行前序、中序、后序和层序遍历，打印结果。
层序遍历通过队列，从上到下、从左到右访问二叉树的节点。
这段代码包括了基本的二叉树操作和遍历方式，可以作为二叉树学习的参考或实现

*/
